/**
 * 96.不同的二叉搜索树
 */
public class Exerciser12 {
    public int numTrees(int n) {
        // dp[i]: 节点个数为i的时候，一共有多少个二叉搜索树
        int[] dp = new int[n + 1];
        // 初始化：空树 也是一个二叉搜索树
        dp[0] = 1;
        for(int i = 1;i <= n;i++) {
            for(int j = 1;j <= i;j++) {
                // 以1到i位置的值都作为根节点的时候，分别去求对应的二叉搜索树，再把所有的进行加起来
                // 这个也称为 卡特兰数
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
}
